\section{Tree method}

\begin{enumerate}[(a)]

	%A
	\item $A \models B \rightarrow C$ then $B \models A \rightarrow C$
		
		$\forall x (M(x,A) \rightarrow (M(x.B) \rightarrow M(x,C))) \models \forall x (M(x,B) \rightarrow (M(x,A) \rightarrow M(x,C)))$
		
		\begin{figure}[!ht]
				\qtreepadding=7pt
					\Tree [.{%
										\begin{tabular}{rll}
										 *1. &$\forall x (M(x,A) \rightarrow (M(x,B) \rightarrow M(x,C)))$					&Premiss 1	\\
											2. &$\neg \forall x (M(x,B) \rightarrow (M(x,A) \rightarrow M(x,C)))$												&$\neg$ Conclusion \\
											3. &$\exists x \neg (M(x,B) \rightarrow (M(x,A) \rightarrow M(x,C)))$												&$\forall$ Rule 1 \\
											4. &$\neg (M(d,B) \rightarrow (M(d,A) \rightarrow M(d,C)))$																	&$\exists$ Rule 3 d \\
											5. &$M(d,B) \wedge \neg(M(d,A) \rightarrow M(d,C))$																					&$\rightarrow$ Rule 4 \\
											6. &$M(d,B)$																																								&$\wedge$ Rule 5	\\
											7. &$\neg (M(d,A) \rightarrow M(d,C))$																											&$\wedge$ Rule 5	\\
											8. &$M(d,A) \wedge \neg M(d,C)$																															&$\rightarrow$ Rule 7 \\
											9. &$M(d,A)$																																								&$\wedge$ Rule 8 \\
											10.&$\neg M(d,C)$																																						&$\wedge$ Rule 8 \\
											11.&$M(d,A) \rightarrow (M(d,B) \rightarrow M(d,C))$																				&$\forall$ Rule 1,d	\\
											12.&$\neg M(d,A) \vee (M(d,B) \rightarrow M(d,C))$																					&$\rightarrow$ Rule 11 \\
										\end{tabular}
									}
									[.{
											\begin{tabularx}{150pt}{rXl}
												13. &$\neg M(d,A)$													&$\vee$ Rule 12
											\end{tabularx}
										}
										{
											$\otimes$ (9, 13)
										}
									]
									[.{B
											\begin{tabularx}{200pt}{rXl}
												14. &$ M(d,B) \rightarrow M(d,C)$					&$\vee$ Rule 12 \\
												15. &$ \neg M(d,B) \vee M(d,C)$						&$\rightarrow$ Rule 14 \\
											\end{tabularx}
										}
										[.{
												\begin{tabularx}{150pt}{rXl}
													16. &$\neg M(d,B)$											&$\vee$ Rule 16 \\
												\end{tabularx}
											}
											{
												$\otimes$ (6, 16)
											}
										]
										[.{
												\begin{tabularx}{150pt}{rXl}
													17. &$M(d,C)$													&$\vee$ Rule 12 \\
												\end{tabularx}
											}
											{
												$\otimes$ (10, 17)
											}
										]
									]
								]
				\end{figure}
				
				The claim is correct because all branches of the tree closes and lead to a contradiction. This means that there does not exists a model for the collection $<$$\forall x (M(x,A) \rightarrow (M(x,B) \rightarrow M(x,C))), \neg \forall x (M(x,B) \rightarrow (M(x,A) \rightarrow M(x,C)))$$>$. Because this collection is not fullfillable, and this collection is the negation of the original claim, it is proven that the original claim must be correct.
	%B
	\clearpage
	\item $\exists x(P(x) \wedge \neg M(x)), \exists x(M(x) \wedge \neg S(x)) \models \exists x(P(x) \wedge \neg S(x)) $
	
		\begin{figure}[!ht]
		\qtreepadding=7pt
			\Tree [.{%
								\begin{tabular}{rll}
									1. &$\exists x(P(x) \wedge \neg M(x))$									& Premiss 1 \\
									2. &$\exists x(M(x) \wedge \neg S(x))$									& Premiss 2 \\
									3. &$\neg \exists (P(x) \wedge \neg S(x))$						&$\neg$ Conclusion \\
								 *4. &$\forall x\neg (P(x) \wedge \neg S(x) )$						&$\exists$ Rule 3 \\
									5. &$P(a) \wedge \neg M(a)$														&$\exists$ Rule 1,a \\
									6. &$P(a)$																						&$\wedge$ Rule 5 \\
									7. &$\neg M(a)$																				&$\wedge$ Rule 5 \\
									8. &$M(b) \wedge \neg S(b)$														&$\exists$ Rule 2,b \\
									9. &$M(b)$																						&$\wedge$ Rule 8 \\
									10.&$\neg S(b)$																				&$\wedge$ Rule 8 \\
									11.&$\neg (P(a) \wedge  \neg S(a))$										&$\forall$ Rule 1,a \\
									12.&$\neg P(a) \vee \neg \neg S(a)$										&$\wedge$ Rule 11 \\
									13.&$\neg(P(b) \wedge \neg S(b)$											&$\forall$ Rule 4,b \\
									14.&$\neg P(b) \vee \neg \neg S(b)$										&$\wedge$ Rule 13 \\
								\end{tabular}
							}
							[.{
								\begin{tabularx}{150pt}{rXl}
									15. &$\neg P(a)$											&$\vee$ Rule 12 \\
								\end{tabularx}
								}
								{
									$\otimes$ (6, 15)
								}
							]
							[.{
									\begin{tabularx}{150pt}{rXl}
										16. &$\neg \neg S(a)$											&$\vee$ Rule 12 \\
										17. &$S(a)$																&$\neg$ Rule 16 \\
									\end{tabularx}
								}
								{
									\begin{tabularx}{150pt}{rXl}
										18. &$\neg P(b)$													&$\vee$ Rule 14 \\
									\end{tabularx}
								}
								[.{
									\begin{tabularx}{150pt}{rXl}
										19. &$\neg \neg S(b)$											&$\vee$ Rule 14 \\
									\end{tabularx}
									}
									{
										$\otimes$ (10, 19)
									}
								]
							]
						]
		\end{figure}
		
		Not all the branches of the tree are closed, when we go up from node 18 to the root we will find the following formulas that form the counterexample:
		
		\begin{enumerate}[1]
			\item $\forall x\neg (P(x) \wedge \neg S(x) )$
			\item $P(a)$
			\item $\neg M(a)$
			\item $M(b)$
			\item $\neg S(b)$	
			\item $S(a)$
			\item $\neg P(b)$	
		\end{enumerate}
		
		The interpretation $i$ that makes all the formulas above true shows that the original claim is not true.
		
		$P^i = R_0$, $M^i = R_1$, $S^k = R_2$, $a = b_0$, $b	= b_1$
				
		$K$= $<$$D;R_0,R_1,R_2;b_0,b_1$$>$
		
		\begin{align*}
			D   &= \left\{ b_0, b_1 \right\}		\\
			R_0 &= \left\{ b_0 \right\}					\\
			R_1 &= \left\{ b_1 \right\}					\\
			R_2 &= \left\{ b_0 \right\}					\\
		\end{align*}
		
		Counterexample:\\
		$\exists x(P(x) \wedge \neg M(x))$, equals true for $x=b_0$					\\
		$\exists x(M(x) \wedge \neg S(x))$, equals true for $x=b_1$					\\
		$\exists (P(x) \wedge \neg S(x))$, is not true for $x=b_0$ or $x=b_1$		\\
	\clearpage
	
	%C
	
	\item $	\forall x Q(x) \rightarrow \forall x P(x) \models \exists x(Q(x)\rightarrow P(x)) $
	\
		\begin{figure}[!ht]
		\qtreepadding=7pt
			\Tree [.{%
								\begin{tabular}{rll}
									1. &$\forall x Q(x) \rightarrow \forall x P(x)$				& Premiss 1 \\
									2. &$\neg\exists x(Q(x)\rightarrow P(x))$							&$\neg$ Conclusion \\
								  3. &$\neg\forall x Q(x) \vee \forall x P(x)$					&$\rightarrow$ Rule 1 \\
									4. &$\forall x\neg(Q(x)\rightarrow P(x))$							&$\exists$ Rule 2 \\
								 *5. &$\forall x(Q(x)\wedge \neg P(x))$										&$\neg$ Rule 4 \\
								\end{tabular}
							}
							[.{
								\begin{tabularx}{160pt}{rXl}
									6. &$\neg \forall x Q(x)$											&$\vee$ Rule 3 \\
								  8. &$\exists x \neg Q(x)$											&$\forall$ Rule 6 \\
								  9. &$\neg Q(a) $																&$\exists$ Rule 8 \\
								  10.&$Q(a) \wedge \neg P(a)$										&$\forall$ Rule 5 \\
								  11.&$Q(a)$																		&$\wedge$ Rule 10 \\
								\end{tabularx}
								}
								{
									$\otimes$ (11, 9)
								}
							]
							[.{
									\begin{tabularx}{160pt}{rXl}
									  *7. &$\forall x P(x)$											&$\vee$ Rule 3 \\
									  12. &$P(a)$																&$\forall$ Rule 7 \\
										13. &$Q(a)\wedge \neg P(a)$								&$\forall$ Rule 5 \\
										14. &$\neg P(a)$													&$\wedge$ Rule 13 \\
									\end{tabularx}
								}
									{
									$\otimes$ (14, 12)
								}
							]
						]
		\end{figure}
		
		The claim is correct because all branches of the tree closes and lead to a contradiction. This means that there does not exists a model for the collection $<$$\forall x Q(x) \rightarrow \forall x P(x)  ,\neg (\exists x(Q(x)\rightarrow P(x)))$$>$. Because this collection is not fullfillable, and this collection is the negation of the original claim, it is proven that the original claim must be correct.
	
\end{enumerate}
\clearpage